package hot;

public class erqijiu {
    public static int numSquares(int n) {
        int m=(int)Math.sqrt(n);
        int[][] f=new int[m+1][n+1];
        for(int j=1;j<=n;j++){
            f[0][j]=-1;
        }
        for(int i=1;i<m+1;i++){
            int square=i*i;
            for(int j=0;j<=n;j++){
                f[i][j]=f[i-1][j];
                if(j-square>=0&&f[i][j-square]!=-1){
                    if(f[i][j]==-1){
                        f[i][j]=f[i][j-square]+1;
                    }else{
                        f[i][j]=Math.min(f[i][j],f[i][j-square]+1);
                    }
                }
            }
        }
        return f[m][n];
    }

    public static void main(String[] args) {
        int n=12;
        int i = numSquares(n);
        System.out.println(i);

    }
}
